public class LeetCode395 {
    public int longestSubstring(String s, int k) {
        return divideAndConquer(s, 0, s.length(), k);
    }

    private int divideAndConquer(String s, int start, int end, int k) {
        // 子串长度小于k时，直接返回0
        if (end - start < k) {
            return 0;
        }

        // 统计字符频率
        int[] freq = new int[26];
        for (int i = start; i < end; i++) {
            freq[s.charAt(i) - 'a']++;
        }

        // 检查每个字符是否满足条件，如果不满足则以此为界分割字符串
        for (int mid = start; mid < end; mid++) {
            char c = s.charAt(mid);
            // // 如果当前字符不满足条件
            if (freq[c - 'a'] < k && freq[c - 'a'] > 0) {
                int left = divideAndConquer(s, start, mid, k);      // 分割左半部分
                int right = divideAndConquer(s, mid + 1, end, k);// 分割右半部分
                // 返回两部分中的最大值
                return Math.max(left, right);
            }
        }
        // 如果所有字符都满足条件，则返回当前子串的长度
        return end - start;
    }
}
